public class Solution5 {
    /*public String longestPalindrome(String s) {
        int front, back, middle;
        String res = s.substring(0, 1);
        char[] value = s.toCharArray();
        for (int i = 1; i < value.length; i++) {
            char c = value[i];
            if (c == value[i - 1]) {
                front = i - 2;
                back = i + 1;
                String temp = getPalindrome(value, front, back);
                if (temp.length() > res.length()) {
                    res = temp;
                }
            }
            if (i >= 2 && c == value[i - 2]) {
                front = i - 3;
                back = i + 1;
                String temp = getPalindrome(value, front, back);
                if (temp.length() > res.length()) {
                    res = temp;
                }
            }
        }
        return res;
    }

    private String getPalindrome(char[] value, int left, int right) {
        while (left >= 0 && right < value.length) {
            if (value[left] != value[right]) {
                break;
            }
            left--;
            right++;
        }
        return String.valueOf(value, left + 1, right - left - 1);
    }*/
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];     //dp[i][j]为true表示s[i...j]（左闭右闭）为回文
        for (int i = 0; i < dp.length; i++) {
            boolean[] booleans = dp[i];
            for (int j = 0; j < booleans.length; j++) {
                booleans[i] = false;
            }
        }
        char[] chars = s.toCharArray();
        int maxlength = 0;
        int left = 0, right = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i <= 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                    if (dp[i][j] && j - i + 1 > maxlength) {
                        maxlength = j - i + 1;
                        left = i;
                        right = j;
                    }
                }
            }
        }
        return s.substring(left, right + 1);
    }
}
